Description

100. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100].
-10^4 <= Node.val <= 10^4

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 判斷兩棵樹是否相同

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 如果兩棵樹都是空的，則它們是相同的
    if (p == NULL && q == NULL) {
        return true;
    }
    
    // 如果一棵樹是空的，而另一棵不是，則它們不同
    if (p == NULL || q == NULL) {
        return false;
    }
    
    // 如果當前節點的值不相同，則兩棵樹不同
    if (p->val != q->val) {
        return false;
    }

    // 遞迴比較left, right subtree
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

Testing

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//定義binary tree node
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 判斷兩棵樹是否相同

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 如果兩棵樹都是空的，則它們是相同的
    if (p == NULL && q == NULL) {
        return true;
    }
    
    // 如果一棵樹是空的，而另一棵不是，則它們不同
    if (p == NULL || q == NULL) {
        return false;
    }
    
    // 如果當前節點的值不相同，則兩棵樹不同
    if (p->val != q->val) {
        return false;
    }

    // 遞迴比較左右子樹
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

// 輔助函數，創建新節點
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 測試函數
void testIsSameTree() {
    // 建立測試樹1 [1,2,3]
    struct TreeNode* tree1 = createNode(1);
    tree1->left = createNode(2);
    tree1->right = createNode(3);

    // 建立測試樹2 [1,2,3]
    struct TreeNode* tree2 = createNode(1);
    tree2->left = createNode(2);
    tree2->right = createNode(3);

    // 測試兩棵樹是否相同
    printf("Test case 1 (should be true): %s\n", isSameTree(tree1, tree2) ? "true" : "false");

    // 建立測試樹3 [1,2]
    struct TreeNode* tree3 = createNode(1);
    tree3->left = createNode(2);

    // 建立測試樹4 [1,null,2]
    struct TreeNode* tree4 = createNode(1);
    tree4->right = createNode(2);

    // 測試兩棵樹是否相同
    printf("Test case 2 (should be false): %s\n", isSameTree(tree3, tree4) ? "true" : "false");
}

// 主測試函數
int main() {
    testIsSameTree();
    return 0;
}